/*
Source : https://leetcode.com/problems/4sum/
Author : nflush@outlook.com
Date   : 2016-08-23
*/

/*
18. 4Sum

    Total Accepted: 83950
    Total Submissions: 339547
    Difficulty: Medium

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

Subscribe to see which companies asked this question
*/

class Solution { // 16ms
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ret;
        vector<int> asn;
        if (nums.size() >= 4){
            std::sort(nums.begin(), nums.end());
            int max = nums.size();
            int b1 = nums[max-1];
            int b2 = nums[max-2] + b1;
            int b3 = nums[max-3] + b2;
            int m,j,k,i;
            for (m =0 ; m < max -3; m++){
                if (nums[m] + b3 >= target) break;
            }
            for (;m<max-3;m++){
                if(m!=0&&nums[m]==nums[m-1]) continue;
                if(nums[m]*4 > target) break;
                for (i=m+1;i<max-2;i++){
                    if(nums[i] + b2 < target - nums[m]) continue;
                    if(nums[i] * 3 > target - nums[m]) break;
                    if(i!=m+1&&nums[i]==nums[i-1]) continue;
                    int tzx = target - nums[m] - nums[i];
                    for (j=i+1, k=max-1;j<k;){
                        if(j!=i+1&&nums[j]==nums[j-1]){
                            j++;
                            continue;
                        }
                        int sum = nums[j]+nums[k];
                        if (sum == tzx){
                            asn.clear();
                            asn.push_back(nums[m]);
                            asn.push_back(nums[i]);
                            asn.push_back(nums[j]);
                            asn.push_back(nums[k]);
                            ret.push_back(asn);
                            j++;
                        } else if(sum > tzx){
                            k--;
                        } else {
                            j++;
                        }
                    }
                }
            }
        }
        return std::move(ret);
    }
};

class Solution { // 16ms
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ret;
        vector<int> asn;
        if (nums.size() >= 4){
            std::sort(nums.begin(), nums.end());
            int max = nums.size();
            int b1 = nums[max-1];
            int b2 = nums[max-2] + b1;
            int b3 = nums[max-3] + b2;
            int m,j,k,i;
            int z1,z2,z3;
            for (m =0 ; m < max -3; m++){
                if (nums[m] + b3 >= target) break;
            }
            while (m<max-3){
                z1 = nums[m];
                if(z1 * 4 > target) break;

                for  (i=m+1;i<max-2;i++){
                    if (nums[i] + b2 + z1 >= target) break;
                }

                while (i<max-2){
                    z2 = nums[i];
                    if(z2 * 3 + z1 > target) break;

                    int tzx = target - z1 - z2;

                    for (j=i+1; j<max-1;j++){
                        if (nums[j]+b1 >= tzx) break;
                    }

                    for(k=max-1;j<k;){
                        z3 = nums[j]; 
                        if (z3*2 > tzx) break;
                        int sum = nums[j]+nums[k];
                        if (sum == tzx){
                            asn.clear();
                            asn.push_back(z1);
                            asn.push_back(z2);
                            asn.push_back(z3);
                            asn.push_back(nums[k]);
                            ret.push_back(asn);
                            do{
                                j++;
                            } while(j<k&&nums[j]==z3);
                        } else if(sum > tzx){
                            do{
                                k--;
                            } while(j<k&&nums[k]==nums[k+1]);
                        } else {
                            do{
                                j++;
                            } while(j<k&&nums[j]==z3);
                        }
                    }
                    do{
                        i++;
                    }while(i<max&&nums[i]==z2);
                }
                do{
                     m++;
                }while(m<max&&nums[m]==z1);
            }
        }
        return std::move(ret);
    }
};

class Solution { // 88ms
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ret;
        vector<int> asn;
        if (nums.size() >= 4){
            std::sort(nums.begin(), nums.end());
            int max = nums.size();
            int m,j,k,i;
            for (m =0;m<max-3;m++){
                if(m!=0&&nums[m]==nums[m-1]) continue;
                for (i=m+1;i<max-2;i++){
                    if(i!=m+1&&nums[i]==nums[i-1]) continue;
                    int tzx = target - nums[m] - nums[i];
                    for (j=i+1, k=max-1;j<k;){
                        if(j!=i+1&&nums[j]==nums[j-1]){
                            j++;
                            continue;
                        }
                        int sum = nums[j]+nums[k];
                        if (sum == tzx){
                            asn.clear();
                            asn.push_back(nums[m]);
                            asn.push_back(nums[i]);
                            asn.push_back(nums[j]);
                            asn.push_back(nums[k]);
                            ret.push_back(asn);
                            j++;
                        } else if(sum > tzx){
                            k--;
                        } else {
                            j++;
                        }
                    }
                }
            }
        }
        return std::move(ret);
    }
};

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int i=0,j=0,k;
        int max = nums.size();
        std:sort(nums.begin(), nums.end());
        vector<vector<int>> ret;
        vector<int> asn;
        for (i=0;i<max-2;i++){
            if(i!=0&&nums[i]==nums[i-1]) continue;
            for (j=i+1, k=max-1;j<k;){
                if(j!=i+1&&nums[j]==nums[j-1]){
                    j++;
                    continue;
                }
                int sum = nums[i]+nums[j]+nums[k];
                if (sum == 0){
                    asn.clear();
                    asn.push_back(nums[i]);
                    asn.push_back(nums[j]);
                    asn.push_back(nums[k]);
                    ret.push_back(asn);
                    j++;
                } else if(sum > 0){
                    k--;
                } else {
                    j++;
                }
            }
        }
        return ret;
    }
};

